package main

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main()  {
	root:=TreeNode{1,{3,{5,nil,nil},{3,nil,nil}},{2,nil,{9,nil,nil}}}
	println(width(root))

}

func widthOfBinaryTree(root *TreeNode) int {
	left, right := width(root, 0, 0)
	return right - left + 1
}

func width(root *TreeNode, cleft int, cright int) (int, int) {
	left := 0
	right := 0
	if root.Left != nil {
		l, r := width(root.Left, cleft + 1, cright-1)
		if left < l {
			left = l
		}
		if right < r {
			right = r
		}
	}
	if root.Right != nil {
		l, r := width(root.Right, cleft-1, cright+1)
		l -= 1
		if left < l {
			left = l
		}
		if right < r {
			right = r
		}
	}
	return left, right
}
